package _go

/*52. N皇后 II
难度
困难

313

收藏

分享
切换为英文
接收动态
反馈
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。



示例 1：


输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：

输入：n = 1
输出：1


提示：

1 <= n <= 9
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。*/
//双O1的解法
func totalNQueens(n int) int {
	result := [9]int{1, 0, 0, 2, 10, 4, 40, 92, 352}
	return result[n-1]
}

//与N皇后类似s
var total int

func totalNQueens(n int) int {
	total = 0
	if n == 1 {
		return 1
	}

	queens := make([]int, n)
	for i := 0; i < n; i++ {
		queens[i] = -1
	}

	l, r, lie := map[int]bool{}, map[int]bool{}, map[int]bool{}

	bTree(queens, 0, n, l, r, lie)

	return total
}

func bTree(queens []int, row, n int, l, r, lie map[int]bool) {
	if row == n {
		total++
		return
	}
	for i := 0; i < n; i++ {
		lKey, rKey := row-i, row+i
		if l[lKey] || r[rKey] || lie[i] {
			continue
		}

		queens[row], l[lKey], r[rKey], lie[i] = i, true, true, true
		bTree(queens, row+1, n, l, r, lie)
		queens[row], l[lKey], r[rKey], lie[i] = -1, false, false, false
	}
}
